package com.mango.leet.code.middle;

/**
 * 剑指 Offer II 053. 二叉搜索树中的中序后继
 * @Author: mango
 * @Date: 2022/4/14 10:31 下午
 */

import java.util.*;

/**
 * 给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。
 *
 * 节点 p 的后继是值比 p.val 大的节点中键值最小的节点，即按中序遍历的顺序节点 p 的下一个节点。
 *
 *  
 *
 * 示例 1：
 *
 *
 *
 * 输入：root = [2,1,3], p = 1
 * 输出：2
 * 解释：这里 1 的中序后继是 2。请注意 p 和返回值都应是 TreeNode 类型。
 * 示例 2：
 *
 *
 *
 * 输入：root = [5,3,6,2,4,null,null,1], p = 6
 * 输出：null
 * 解释：因为给出的节点没有中序后继，所以答案就返回 null 了。
 *  
 *
 * 提示：
 *
 * 树中节点的数目在范围 [1, 104] 内。
 * -105 <= Node.val <= 105
 * 树中各节点的值均保证唯一。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/P5rCT8
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LCoffer_53 {
    /**
     * Definition for a binary tree node.
     */ public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
      }

    class Solution {
        public TreeNode inorderSuccessor2(TreeNode root, TreeNode p) {
            TreeNode result = null;
            while (root != null){
                // 如果当前值大于查找的值，则继续在左子树中找
                if(root.val > p.val){
                    result = root;
                    root = root.left;
                }else{
                    // 如果当前值小于查找的值，则继续在右子树中找
                    root = root.right;
                }
            }
            return result;
        }
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            Queue<TreeNode> result = new LinkedList<>();
            process(root,result);
            while (!result.isEmpty()){
                if(result.poll().val == p.val){
                    break;
                }
            }
            return !result.isEmpty() ? result.poll() : null;
        }

        private void process(TreeNode root, Queue<TreeNode> result) {
            if(root == null){
                return ;
            }
            process(root.left,result);
            result.add(root);
            process(root.right,result);
        }
    }
}
